#include "list.h"
#include "dict.h"
#include "simple.h"
#include <string.h>
#include <stdio.h>
#include <stdarg.h>


#ifdef PYTHON
#include <python2.4/Python.h>
#endif

#define sp_cat elog_sp_cat

/* TODO: faster dictionaries
 *  I'm not going to implement binary search as I think it's wrong for the problem.
 * 	I'm going to simple have searches be done going outwards from the last result.
 * 	So, you go prev?, next?, prev->prev?, next->next?.  See?
 */

struct dict *dict_new()
{
  struct dict *ret = malloc(sizeof *ret);
  ret->root = NULL;
  ret->size = 0;
  ret->fast_mode = 0;
  ret->last_indice = NULL;
  ret->ref = 1;
  ret->lock = thrd_lock_new();
#ifdef TEST
  ret->searches = 0;
#endif
  return ret;
}

struct dict_value *dict_value_new()
{
	struct dict_value *ret = malloc(sizeof *ret);
	ret->next = NULL;
	ret->last = NULL;
	ret->name = NULL;
	ret->value = NULL;
	ret->free = 0;
	ret->to_dict = NULL;
	ret->to_string = NULL;
	ret->type = 0;
	ret->hidden = 0;
	
	return ret;
}

void dict_value_free_value(struct dict_value *val)
{
	if (val->free) {
		if (val->type == DICT_TYPE_STR ||
			val->type == DICT_TYPE_OBJ ||
			val->type == DICT_TYPE_INT)
			free(val->value);
		else if (val->type == DICT_TYPE_LST)
			list_unref(val->value);
		else if (val->type == DICT_TYPE_DCT)
			dict_unref(val->value);
	}
}

void dict_value_free(struct dict_value *val)
{
	free(val->name);
	dict_value_free_value(val);
	free(val);	
}



void dict_free(struct dict *d)
{
  struct dict_value *p = d->root;
  while (p) {
	struct dict_value *t = p;
	p = p->next;
	dict_value_free(t);
  }
  thrd_lock_free(d->lock);
  free(d);
}


void dict_ref(struct dict *d)  {  d->ref += 1;  }
void dict_unref(struct dict *d)
{
  d->ref -= 1;
  if (d->ref <= 0) {
	dict_free(d);
  }
}


void dict_go_fast(struct dict *d) {  d->fast_mode = 1;  }

void dict_go_right(struct dict *d)  {  d->fast_mode = 0;  }

inline int _dict_cmp_str(const char *a, const char *b)
{
	while (*a)
		if (!(*a++ == *b++))
			return 0; //checks each cell and quits when one is \0

	return !(*a) && !(*b);
}

#define STRCMP(a, b) _dict_cmp_str(a, b)

#ifdef TEST
void _increment_searches(struct dict *d, unsigned int searches)
{
	d->avg_comparisons = (d->avg_comparisons*((double)d->searches) + 
				((double)searches)) / ((double)(d->searches+1));
	d->searches += 1;
}
#endif


/*
 * This code is preserved so that you may benchmark for yourself the 
 * difference between brute searching and brute searching from the last use.
 * This code just checks the last use then searches from the beginning.
 *
struct dict_value *_dict_find(struct dict *d, const char *name)
{
	int searches = 0;
	
	if (d->last_indice) {
		searches += 1;
		if (strcmp(d->last_indice->name, name) == 0) {
			_increment_searches(d, searches);
			return d->last_indice;
		}
	}
  struct dict_value *p = d->root;
  while (p) {
	if (p == d->last_indice) {
	  p = p->next;
	  continue;
	}
	searches += 1;
	if (strcmp(p->name, name) == 0) {
	  _increment_searches(d, searches);
	  d->last_indice = p;
	  return p;
	}
	p=p->next;
  }
  _increment_searches(d, searches);
  return NULL;
}
*/

struct dict_value *_dict_find(struct dict *d, const char *name)
{
#ifdef TEST
	int searches = 0;
#endif
	/*	Search backwards and fordwards at the same time!
	 * 
	 */ 
	if (!(d->last_indice))
		d->last_indice = d->root;
	struct dict_value *f = d->last_indice;
	struct dict_value *b = d->last_indice;
	while (f || b) {
		if (f) {
#ifdef TEST
			searches += 1;
#endif
			if (STRCMP(f->name, name)) {
				d->last_indice = f;
#ifdef TEST
				_increment_searches(d, searches);
#endif
				return f;	
			}
			f = f->next;
		}
		if (b) {
#ifdef TEST
		    searches += 1;
#endif
			if (STRCMP(b->name, name)) {
				d->last_indice = b;
#ifdef TEST
				_increment_searches(d, searches);
#endif
				return b;	
			}	
			b = b->last;
		}
	}
#ifdef TEST
	_increment_searches(d, searches);
#endif
	return NULL;
}




void dict_set(struct dict *d, const char *name, void *value)
{
  thrd_lock(d->lock);
  struct dict_value *c = NULL;
  if (!(d->fast_mode)) //don't search in fast mode
	c = _dict_find(d, name);

  if (!c) {
	c = dict_value_new();
	c->name = NULL;
	c->value = NULL;
	c->free = 0;
	c->type = 0;
	struct dict_value *p = d->root;
	d->root = c;
	c->next = p;
	if (p)
		p->last = c;
	
	c->last = NULL;
	d->last_indice = c;
	++(d->size);
  } //c exists now:

  if (c->name) { //we have it already
  	if (c->value != value) {
		dict_value_free_value(c);
		c->value = value;
  	}
  } else {//it's new
	sp_cat(&(c->name), name, NULL);
	c->value = value;
	c->free = 0;
	c->type = DICT_TYPE_STR;
  }
  thrd_unlock(d->lock);
}


void *dict_rget(struct dict *d, ...)
{
 	thrd_lock(d->lock);
 	
  	va_list ap;
	va_start(ap, d);
	
	struct dict *subdict = d;
	const char *arg = va_arg(ap, const char *);
	while (arg) {
		struct dict_value *ptr = _dict_find(subdict, arg);
		
		const char *arg2 = va_arg(ap, const char *);
		if (!arg2) {
			thrd_unlock(d->lock);
			va_end(ap);
			if (ptr)
				return ptr->value;
			else
				return NULL;	
		}
		subdict = ptr->value;
		arg = arg2;
	}
	//assume the following should never happen...
  	va_end(ap);
  	thrd_unlock(d->lock);
  	return NULL;
}

void *dict_get(struct dict *d, const char *name)
{
  thrd_lock(d->lock);  
  struct dict_value *c = _dict_find(d, name);
  void *val = NULL;
  if (c)
	val = c->value;
  thrd_unlock(d->lock);
  return val;
}

void dict_set_free(struct dict *d, const char *name, int stat)
{
  thrd_lock(d->lock);
  struct dict_value *c = _dict_find(d, name);
  if (c)
	c->free = stat;
  thrd_unlock(d->lock);
}

void dict_set_type(struct dict *d, const char *name, int type)
{
  thrd_lock(d->lock);
  struct dict_value *c = _dict_find(d, name);
  if (c) {
	c->type = type;
	if (type == DICT_TYPE_DCT) { 
		dict_ref(c->value);
		c->free = 1;
	}
	else if (type == DICT_TYPE_LST) {
		dict_ref(c->value);
		c->free = 1;
	}
  }
  thrd_unlock(d->lock);
}
int dict_get_type(struct dict *d, const char *name)
{
	thrd_lock(d->lock);
	int ret = -1;
	struct dict_value *c = _dict_find(d, name);
	if (c)
		ret = c->type;
	thrd_unlock(d->lock);	
	return ret;
}

void dict_set_convert(struct dict *d, const char *name, 
					  to_str_t to_string, to_dct_t to_dict)
{
  thrd_lock(d->lock);
  struct dict_value *c = _dict_find(d, name);
  if (c) {
	c->to_string = to_string;
	c->to_dict = to_dict;
  }
  thrd_unlock(d->lock);
}

void dict_print(struct dict *d)
{
	struct dict_value *q = d->root;
	while (q) {
		switch (q->type) {
			case DICT_TYPE_STR:
				printf("String:%s:%s\n", q->name, (char *)q->value);
				break;
			case DICT_TYPE_OBJ:
				printf("Object:%s:%x\n", q->name, (unsigned int)q->value);
				break;	
			case DICT_TYPE_INT:
				printf("Int:%s:%i\n", q->name, *(int *)(q->value));
				break;
			case DICT_TYPE_LST:
				printf("List:%s\n", q->name);
				list_print(q->value);
				break;
			case DICT_TYPE_DCT:
				printf("----\n");
				printf("Dict:%s\n", q->name);
				dict_print(q->value);
				printf("----\n");
				break;
		}
		q=q->next;	
	}
}
struct list *dict_get_list(struct dict *d, const char *name)
{
	if (dict_get_type(d, name) == DICT_TYPE_DCT) {
		struct dict *sub = dict_get(d, name);
		return list_from_dict(sub);
	} else if (dict_get_type(d, name) == DICT_TYPE_LST) {
		return dict_get(d, name);
	}
	else {
		struct list *ret = list_new();
		list_add(ret, dict_get(d, name));
		list_type(ret, dict_get_type(d, name));
		list_free_able(ret, 0); //I own it!
		return ret;
	}
	return NULL;
}

void dict_remove(struct dict *d, const char *name)
{
	struct dict_value *c = _dict_find(d, name);
	if (c) {		
		if (!(c->next) && !(c->last)) {
			d->root = NULL;
			d->last_indice = NULL;
		}
		else if (c->next && !(c->last)) { 
			d->root = c->next;
			d->root->last = NULL;
			d->last_indice = d->root;
		}
		else if (!(c->next) && c->last) {
			c->last->next = NULL;
			d->last_indice = c->last;
		}
		else {
			c->next->last = c->last;
			c->last->next = c->next;
			d->last_indice = c->last;	
		}

		dict_value_free(c);
	}	
}

void dict_set_hidden(struct dict *d, const char *name, int h)
{
	struct dict_value *c = _dict_find(d, name);
	c->hidden = h;
}

int dict_rcheck(struct dict *d, ...)
{
	thrd_lock(d->lock);
 	
  	va_list ap;
	va_start(ap, d);
	
	struct dict *subdict = d;
	const char *arg = va_arg(ap, const char *);
	while (arg) {
		struct dict_value *ptr = _dict_find(subdict, arg);
		if (!ptr) { 
			thrd_unlock(d->lock);
			va_end(ap);
			return 1;
		}
		const char *arg2 = va_arg(ap, const char *);
		if (!arg2) {
			thrd_unlock(d->lock);
			va_end(ap);
			return 0;	
		}
		subdict = ptr->value;
		arg = arg2;
	}
	//assume the following should never happen...
  	va_end(ap);
  	thrd_unlock(d->lock);	
  	return 1;
}

int dict_check(struct dict *d, ...)
{
	if (!d) return 1;
	va_list ap;

	va_start(ap, d);
	
	const char *arg;
	while ((arg = va_arg(ap, const char *))) {
		if (!dict_get(d, arg)) {
			va_end(ap);
			return 1;
		}
	}
	va_end(ap);
	return 0;
}


//the following is not presently thread safe:
#ifdef PYTHON
PyObject *dict_to_py(struct dict *d)
{
  PyObject *nue = PyDict_New();

  struct dict_value *p = d->root;
  while (p) {
	PyObject *t;
	if (p->type == DICT_TYPE_STR) 
	  t = PyString_FromString((char *)p->value); 
	else if (p->type == DICT_TYPE_INT) 
	  t = PyInt_FromLong((long)(p->value)); 
	else if (p->type == DICT_TYPE_DCT)
	  t = dict_to_py(p->value); //recurse
	else if (p->type == DICT_TYPE_OBJ)
	  t = p->value;

	if (PyDict_SetItemString(nue, p->names, t))
	  printf("Failed to set something for py dict\n");
	p = p->next;
  }
  p = d->root;
  while (p) {
	PyObject *t;
	if (p->type == DICT_TYPE_STR) 
	  t = PyString_FromString((char *)p->value); 
	else if (p->type == DICT_TYPE_INT) 
	  t = PyInt_FromLong((long)(p->value)); 
	else if (p->type == DICT_TYPE_DCT)
	  t = dict_to_py(p->value); //recurse
	else if (p->type == DICT_TYPE_OBJ)
	  t = p->value;

	if (PyDict_SetItemString(nue, p->names, t))
	  printf("Failed to set something for py dict\n");
	p=p->next;
  }
  return nue;
}
void py_to_dict(struct dict *d, PyObject *p)
{
  struct dict_value *q = d->root;
  while (q) {
	struct dict_value *n = q->next;
	if (q->free)
	  free(q->value);
	free(q->name);
	free(q);
	q=n;
  }
  d->root = NULL; //cleared out the old stuff

  //let's throw on the new.
  PyObject *keys = PyDict_Keys(p);
  int c;
  for (c=0; c < PyList_Size(keys); ++c) {
	PyObject *key = PyList_GetItem(keys, c);
	PyObject *value = PyDict_GetItem(p, key);

	if (PyInt_Check(value)) {
	  int *b = malloc(sizeof *b);
	  *b = PyInt_AsLong(value);
	  const char *name = PyString_AsString(key);
	  dict_set(d, name, b);
	  dict_set_type(d, name, DICT_TYPE_INT);
	  dict_set_free(d, name, 1);
	} else if (PyString_Check(value)) {
	  char *val;
	  sp_cat(&val, PyString_AsString(value), NULL);
	  const char *name = PyString_AsString(key);
	  dict_set(d, name, val);
	  dict_set_type(d, name, DICT_TYPE_STR);
	  dict_set_free(d, name, 1);
	} else if (PyDict_Check(value)) {
	  struct dict *t = dict_new(PyDict_Size(value) + 1);
	  py_to_dict(t, value);
	  d->value[c] = t;
	  const char *name = PyString_AsString(key);
	  dict_set(d, name, t);
	  dict_set_type(d, name, DICT_TYPE_DCT);
	  dict_set_free(d, name, 1);
	} else { //assume it's an OBJ type
	  Py_INCREF(value);
	  const char *name = PyString_AsString(key);
	  dict_set(d, name, value);
	  dict_set_type(d, name, DICT_TYPE_OBJ);
	  dict_set_free(d, name, 0);
	}
  }
  Py_XDECREF(keys);
}
#endif


#ifdef TEST

#include <time.h>

struct pointless
{
	int name;
	int value;
};

int random_case(int seed)
{
	int MIN_N = 128;
	int MIN_WORD = 4;
	
	int MAX_N = 1024 - MIN_N;
	int MAX_WORD = 25 - MIN_WORD;
	srand(seed);
	int n = (((float)rand())/((float)RAND_MAX)) * MAX_N + MIN_N;



	char *keys [n+1];
	struct dict *dct = dict_new();
	{
		dict_go_fast(dct);
		int retries = 0;
		int c;
		for (c=0; c < n; ++c) {
			if (retries > n*10) {
				n = c-1;
				break;
			}
			
			int word_size = (((float)rand())/((float)RAND_MAX)) * MAX_WORD + MIN_WORD;
			char word[word_size + 1];	
			int i;
			for (i=0; i < word_size; ++i)
				word[i] = (((float)rand())/((float)RAND_MAX)) * 26 + 65;
			word[word_size] = '\0';
			

			int match = 0;
			//int i;
			for (i=0; i < c; ++i) { //check to make sure it's a new key
				if (STRCMP(keys[i], word)) {
					--c;
					++retries;
					match = 1;
					break;
				}
			} if (match) continue;


			keys[c] = CPY_STR(word);
			
			int *val = HEAP_INT(c);
			dict_set(dct, word, val);
			dict_set_type(dct, word, DICT_TYPE_INT);
			dict_set_free(dct, word, 1);
		}
		dict_go_right(dct);
	}

	keys[n] = NULL;
	int c;
	for (c=0; c < n; ++c) {
		int *val = dict_get(dct, keys[c]);
		if (dict_check(dct, keys[c], keys[c+1], keys[c+2], NULL)) {
			printf("I couldn't retrieve key %s\n", keys[c]);
			for (; c < n; ++c)
				free(keys[c]);  //cleanup keys to avoid a leak
			dict_unref(dct);
			return 0;		
		}
		if (dict_get_type(dct, keys[c]) != DICT_TYPE_INT) {
			printf("Failed to retain type information, %i %i\n", 
								dict_get(dct, keys[c]), c);
			for (; c < n; ++c)
				free(keys[c]);  //cleanup keys to avoid a leak
			dict_unref(dct);
			return 0;	
		}
		if (*val != c) {
			printf("Failed to retain value correctly:%i %i\n", *val, c);
			for (; c < n; ++c)
				free(keys[c]);  //cleanup keys to avoid a leak
			dict_unref(dct);
			return 0;	
		}
		if (c % 10 == 0) {
			dict_remove(dct, keys[c]);
			if (dict_get(dct, keys[c])) {
				printf("Failed to remove value correctly:%s\n", keys[c]);
				return 0;	
			}	
		}
		free(keys[c]);
	}
	int searches = (int)(dct->avg_comparisons);
	dict_unref(dct);
	return searches;
}

void random_test(int seed)
{
	clock_t start = clock();
	printf("Using Seed:%i\n", seed);
	srand(seed);
	int MIN_N = 128;
	int MAX_N = 1024 - MIN_N;	
	int n = (((float)rand())/((float)RAND_MAX)) * MAX_N + MIN_N;
	
	printf("Running %i tests:          |", n);
	fflush(stdout);
	double searches = 0;
	int c;
	for (c=1; c <= n; ++c) {
		if (c % (n/10) == 0) {
			putchar('=');
			fflush(stdout);
		}
		int s = rand();
		int result = random_case(s);
		if (!result) {
			printf("Failed on case %i of %i cases\n", c, n);
			printf("Seed used was %i\n", s);
			return;
		}
		searches += result;
	}
	searches = searches / ((double)c);
	printf("|\nPassed %i cases successfully\n", n);
	clock_t end = clock();
	printf("Average number of String searches Occured:%f\n", searches);
	printf("Time is thrown off by brute force key searches in test code\n");
}



int main(void)
{
	random_test(time(NULL));
	return 0;
	random_case(1647067979);
	return 0;
	
	
	struct dict *dct = dict_new();
	{
		dict_set(dct, "hello", CPY_STR("world"));
		dict_set_free(dct, "hello", 1);
		
		struct dict *dct1 = dict_new();
		{
			dict_set(dct1, "hello", CPY_STR("bob"));
			dict_set_free(dct1, "hello", 1);
			
			dict_set(dct1, "world", CPY_STR("susan"));
			dict_set_free(dct1, "world", 1);
		}
		dict_set(dct, "subdict", dct1);
		dict_set_type(dct, "subdict", DICT_TYPE_DCT);
		dict_set_free(dct, "subdict", 1);
		dict_unref(dct1);
		
		
		dict_set(dct, "hello", CPY_STR("judy"));
		dict_set_free(dct, "hello", 1);
		
		dict_set(dct, "dave", CPY_STR("blah blah"));
		dict_set_free(dct, "dave", 1);

		dict_set(dct, "123", CPY_STR("456"));
		dict_set_free(dct, "123", 1);
		
		dict_set(dct, "commy", CPY_STR("democracy"));
		dict_set_free(dct, "commy", 1);

	}

	int c; //uncomment and time this if you like!
	for (c=0; c < 1024*1024; ++c) {
		dict_get(dct, "hello");
		dict_get(dct, "123");
		struct dict *dct1 = dict_get(dct, "subdict");
		dict_get(dct1, "hello");
		dict_get(dct1, "world");
		dict_get(dct, "commy");
		dict_get(dct, "dave");
	}


	printf("commy:%s\n", dict_get(dct, "commy"));
	printf("subdict:hello:%s\n", dict_get(dict_get(dct, "subdict"), "hello"));
	printf("Compare with:\n");


/*	struct pointless *p = malloc(sizeof *p);
	p->name = 10;
	p->value = 7; //to compare, somewhat, with just looking up in a struct
					// dict is probably 50 times slower in this case.
	int c;
	for (c=0; c < 1024*1024; ++c) {
		if (p->value == 0)
			p->value = -1;
		p->name = p->value;
		p->value = p->name*4;
		p->name = p->value/(p->value*2);
		p->value = p->name;
		p->name = 3*p->name;
		p->name = p->value;
		p->value = p->name/2;			
	}
	printf("Name:%i\n", p->name);
	printf("Value:%i\n", p->value);
	
*/
	dict_print(dct);

	dict_unref(dct);
	return 0;
}

#endif


